package ThirtySixthDay;

import java.util.Arrays;

public class IsBipartite {
    private int[] color;
    private boolean valid;
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        valid = true;
        color = new int[n];
        Arrays.fill(color, 0);
        for (int i = 0; i < n && valid; ++i) {
            if (color[i] == 0) {
                dfs(i, 1, graph);
            }
        }
        return valid;
    }
    public void dfs(int node, int c, int[][] graph) {
        color[node] = c;
        int cNei = c == 1 ? 2 : 1;
        for (int neighbor : graph[node]) {
            if (color[neighbor] == 0) {
                dfs(neighbor, cNei, graph);
                if (!valid) {
                    return;
                }
            } else if (color[neighbor] != cNei) {
                valid = false;
                return;
            }
        }
    }
}
